# -*- coding: utf-8 -*-            
# @Time : 2023/8/2 22:39
# @Author  : lining
# @FileName: 给定前序中序，还原二叉树.py
"""
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
给定中序和先序，还原二叉树,输出层序
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
前序第一个节点是根节点，中序找到这个节点，左边是左子树，右边是右子树，递归
"""
class Node():
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def solution(preorder, inorder):
    """
    preorder:前序
    inorder:中序
    """
    if not preorder:
        return
    if not inorder:
        return
    if len(inorder) == 1:
        preorder.remove(inorder[0])
        return Node(inorder[0])
    root = Node()
    root.value = preorder[0]
    del preorder[0]
    for a, b in enumerate(inorder):
        if b == root.value:
            root.left = solution(preorder, inorder[0:a])
            root.right = solution(preorder, inorder[a+1:])
            return root


preorder = [3,9,11,20,7]
inorder = [11,9,3,20,7]
x = solution(preorder, inorder)
print(x)


